package com.tree;

import com.com.twotestlist.LikedList;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class LinkedBinaryTree implements BinaryTree {
    //方便操作二叉树这样就知道了二叉树的根节点
    private Node root;

    public LinkedBinaryTree(Node root) {
        this.root = root;
    }

    public LinkedBinaryTree() {
    }

    @Override
    public boolean isEmpty() {
        return root==null;
    }

    @Override
    public int size() {
        System.out.println("二叉树的节点数是");
        return size(root);
    }
    private int size(Node root){
        if(root==null){
            return 0;
        }else{
            int n1=size(root.leftChild);
            int n2=size(root.rightChild);
            return n1+n2+1;

        }
    }

    @Override
    public int getHeight() {
        System.out.println("树的高度是");
        return getHeight(root);
    }
    private int getHeight(Node root){
        if(root==null){
            return 0;
        }else{
            int n1=getHeight(root.leftChild);
            int n2=getHeight(root.rightChild);
            return n1>n2?n1+1:n2+1;

        }
    }

    @Override
    public Node findKey(int value) {
        return findKey(value,root);
    }
    private Node findKey(Object value,Node root){
        if(root==null){
            return null;
        }else if(root!=null && root.value==value){
            return root;
        }else{
            Node node1=findKey(value,root.leftChild);
            Node node2=findKey(value,root.rightChild);
            if(node1!=null && node1.value==value)return node1;
            if(node2!=null && node2.value==value)return node2;
            return null;

        }
    }
    @Override
    public void preOrderTraverse() {
       if(root!=null) {
           System.out.print(root.value+" ");
           BinaryTree leftTree=new LinkedBinaryTree(root.leftChild);
           leftTree.preOrderTraverse();
           BinaryTree rightTree=new LinkedBinaryTree(root.rightChild);
           rightTree.preOrderTraverse();
       }
    }

    @Override
    public void inOrderTraverse() {
     System.out.println("中序遍历");
     this.inOrderTraverse(root);
     System.out.println();
    }
    private void inOrderTraverse(Node root){
        if(root!=null){
            inOrderTraverse(root.leftChild);
            System.out.print(root.value+" ");
            inOrderTraverse(root.rightChild);
        }
    }

    @Override
    public void postOrderTraverse() {
        System.out.println("后序遍历");
        postOrderTraverse(root);
        System.out.println();
    }

    @Override
    public void postOrderTraverse(Node root) {
   if(root!=null){
       postOrderTraverse(root.leftChild);
       postOrderTraverse(root.rightChild);
       System.out.print(root.value+" ");
   }
    }


    @Override
    public void inOrderByStack() {

    }

    @Override
    public void preOrderByStack() {
      if(root==null)return;
        Deque<Node> deque=new LinkedList<Node>();

        Node carrent=root;
  while (carrent!=null || !deque.isEmpty()){
      while(carrent!=null){
          deque.push(carrent);
          carrent=carrent.leftChild;
      }

      if(!deque.isEmpty()){
          carrent=deque.pop();
          System.out.print(carrent.value+" ");
          carrent=carrent.rightChild;
      }

  }
    }

    @Override
    public void postOrderByStack() {

    }

    @Override
    public void levelOrderByStack() {
     if(root==null) return;
        Queue<Node> queue=new LinkedList<Node>();
        queue.add(root);
        while (queue.size()!=0){
            int len=queue.size();
            for(int i=0;i<len;i++){
                Node carrent=queue.poll();
                System.out.print(carrent.value+" ");
                if(carrent.leftChild!=null)queue.add(carrent.leftChild);
                if(carrent.rightChild!=null)queue.add(carrent.rightChild);
            }
        }
    }
}
